public class ChainList {
    /**
     * 简单双端双向链表创建，并实现：
     *  增、删、查*/
    public static void main(String[] args) {

    }

    // 创建链表节点
     static class LinkedNode {
        public int value;
        public LinkedNode prev;
        public LinkedNode next;

        public LinkedNode(int value) {
            /**
             * 构造方法*/
            this.value = value;
        }
    }

    // 定义头/尾节点
    public LinkedNode first = null;
    public LinkedNode last = null;

    // 头插节点
    public boolean addFirst(int val) {
        /**
         * 头插节点，判空：
         *  空：新节点为头/尾节点
         *  不为空：新节点后挂头节点，并重新指定头节点*/
        // 1 创建新节点
        LinkedNode node = new LinkedNode(val);

        // 2 插入
        if(this.first == null) {
            // -为空
            this.first = node;
            this.last = node;
        } else {
            // -不为空
            node.next = this.first;
            this.first.prev = node;
            this.first = node;
        }

        // 3 返回
        return true;
    }

    // 尾插节点
    public boolean addLast(int val) {
        /**
         * 尾插节点，判空
         *  空：新节点为头/尾节点
         *  不为空：新节点后挂与旧尾节点后，尾节点重新赋值*/
        // 1 创建新节点
        LinkedNode node = new LinkedNode(val);

        // 2 插入
        if(this.first == null) {
            // -为空
            this.first = node;
            this.last = node;
        } else {
            // -不为空
            this.last.next = node;
            node.prev = this.last;
            this.last = node;
        }

        // 3 返回
        return true;
    }

    // 头删节点
    public boolean popFirst() {
        /**
         * 头删*/
        // 1 判空
        if(this.first == null) {
            // -为空，空不能删（正常应当抛出异常）
            return false;
        } else {
            // -不为空
            if(this.first == this.last) {
                // -只有一个节点时，直接置空
                this.first = null;
                this.last = null;
            } else {
                // -有两个及以上个节点
                this.first.next.prev = null;
                this.first = this.first.next;
            }
        }

        // 2 返回值
        return true;
    }

    // 尾删节点
    public boolean popLast() {
        /**
         * 尾删节点*/
        // 1 判空
        if(this.first == null) {
            return false;
        } else {
            if(this.first == this.last) {
                // -只有一个节点，直接置空
                this.first = null;
                this.last = null;
            } else {
                // 存在两个及以上的节点，消除引用
                this.last.prev.next = null;
                this.last = this.last.prev;
            }
        }

        // 2 返回值
        return true;
    }

    // 删除指定元素
    public boolean remove(int val) {
        /**
         * 删除指定元素*/
        // 1 查找（循环条件就是判空）
        LinkedNode cur = this.first;
        while(cur != null) {
            // -找到
            if(cur.value == val) {
                // -根据其位置进行操作
                if(cur == this.first) {
                    this.popFirst();
                } else if(cur == this.last) {
                    this.popLast();
                } else {
                    // -不为首/尾，也不为空，正常删除逻辑
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                return true;
            }
            cur = cur.next;
        }

        // 3 链表中没有指定元素，返回false
        return false;
    }

    // 判断是否包含某元素
    public boolean contains(int val) {
        /**
         * 判断包含*/
        // 1 遍历链表
        LinkedNode cur = this.first;
        while(cur != null) {
            if(cur.value == val) {
                return true;
            }
            cur = cur.next;
        }

        // 2 出循环就是没有找到
        return false;
    }

}







































